This paper is concerned with solving nonconvex learning problems with foldedconcave penalty. Despite that their global solutions entail desirablestatistical properties, they lack optimization techniques that guarantee globaloptimality in a general setting. In this paper, we show that a class ofnonconvex learning problems are equivalent to general quadratic programs. Thisequivalence facilitates us in developing mixed integer linear programmingreformulations, which admit finite algorithms that find a provably globaloptimal solution. We refer to this reformulation-based technique as the mixedinteger programming-based global optimization (MIPGO). To our knowledge, thisis the first global optimization scheme with a theoretical guarantee for foldedconcave penalized nonconvex learning with the SCAD penalty [J. Amer. Statist.Assoc. 96 (2001) 1348-1360] and the MCP penalty [Ann. Statist. 38 (2001)894-942]. Numerical results indicate a significant outperformance of MIPGO overthe state-of-the-art solution scheme, local linear approximation and otheralternative solution techniques in literature in terms of solution quality.
展开▼
